Certain memory devices (e.g., flash memory) are prone to a wear-out condition: these memories can only survive a number of update (rewrite or erase and write) cycles, although the number can be quite large (one hundred thousand or more). To compensate for this condition, these memory devices may employ a process called wear leveling, which involves monitoring relative use of memory areas and a mapping between logical and physical areas of a memory to ensure that all physical areas of the memory wear down at similar rates. Wear leveling helps increase the life span of the memory device.
Many prior art techniques have been developed for wear leveling. The functionality associated with these techniques usually is implemented in the flash translation layer (FTL) and involves maintaining a look-up table that maps logical block of memory to physical block of memory. This look-up table requires roughly one word of state for every memory block. For memories that allow fine-grained updates, maintaining such a translation table at the granularity of individual update units would require very large tables, with a consequent reduction in normal memory capacity.